package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/3 14:55
 */
public class J56 {

    /**
     * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
     */
    public static int[] singleNumbers(int[] nums) {
        if (nums.length == 2) {
            return nums;
        }
        int eor = 0;
        for (int num : nums) {
            eor ^= num;
        }
        // 此时eor = 那两个数异或 a^b;
        // 且eor有1的地方 a和b一定不同, 所以随便找个有1的位置.把数组分成两份
        // 再异或一边就可以找到其中的一个数 a | b
        // 最后再用 eor ^ a = b   |    eor ^ b = a
        int last1Num = eor & (~eor + 1);  // 找到最后一个1的位置
        int a = 0;
        for (int num : nums) {
            // 把数组分成两份
            if ((num & last1Num) != 0) {
                a ^= num;
            }
        }
        int b = eor ^ a;
        return new int[]{a, b};
    }

    /** https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/ */
    /**
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     */
    public static int singleNumber(int[] nums) {
        // 思路, 来一个32位的辅助数组, 统计二进制所有1出现的次数, 最后取余与3模!=0 就是答案位有1的地方.
        int[] count = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    count[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }


    // for test
    public static void main(String[] args) {
        /*int[] nums = {4, 1, 4, 6};
        int[] ans = singleNumbers(nums);
        System.out.println(Arrays.toString(ans));*/

        int[] nums = {9,1,7,9,7,9,7};
        System.out.println(singleNumber(nums));
    }

}
